/*
Problem Description
There are many lamps in a line. All of them are off at first. A series of operations are carried out on these lamps. On the i-th operation, the lamps whose numbers are the multiple of i change the condition ( on to off and off to on ).
Input
Each test case contains only a number n ( 0< n<= 10^5) in a line.
Output
Output the condition of the n-th lamp after infinity operations ( 0 - off, 1 - on ).
Sample Input
1
5
Sample Output
1
0

Hint

Consider the second test case:

The initial condition   : 0 0 0 0 0 …
After the first operation : 1 1 1 1 1 …
After the second operation : 1 0 1 0 1 …
After the third operation : 1 0 0 0 1 …
After the fourth operation : 1 0 0 1 1 …
After the fifth operation : 1 0 0 1 0 …

The later operations cannot change the condition of the fifth lamp any more. So the answer is 0.
 */
package com.yuan.algorithms.practice201512;

import java.util.Scanner;

/**
 * @author YouYuan
 * <br>E-mail:1265161633@qq.com
 * <br>创建时间：2015年12月5日 上午10:22:30
 * <br>说明:有很多盏灯在一条线上，初始全为0，进行n次操作，每次操作都按下能被n整除的编号的灯的开关（0变1,1变0），问操作后第n盏灯的状态。
 * 			只需求解n的因子个数即可。
 * 	      规律：只有处于n*n状态的灯才会是亮的。
 */
public class 开关灯问题 {

	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		while(in.hasNext()) {
			int n = in.nextInt();
			int sum = f(n);
			System.out.println(sum&1);
		}
	}


	/**
	 * 快速求解因子数的算法。时间复杂度sqrt(n)，暂不支持负数。
	 * 
	 * 假设存在一个正整数 K,使得 K * M = N, 且 K 不在 1, sqrt(N)之间，且M 为正整数 那么 M必在(1, sqrt(N))之间，否则 K*M >sqrt(N)*sqrt(N) = N,与 K*M = N矛盾 即只要存在两个正整数K, M,使得 K * M = N,那么K，
	 * M中必有一个在[1, sqrt(N)]区间中
	 *
	 * @param n (n>0)
	 * @return
	 */
	private static int f(int n) {
		if (n <= 2) {
			return n;
		}
		int sum = 2;// 1和n必定为因子
		final int sqrt_N = (int) Math.sqrt(n);
		for (int i = 2; i <= sqrt_N; i++) {
			if (n % i == 0) {
				// 去除重复元素，重复因子的出现是在sqrt(N)的附近。比如 4 = 2 * 2；那么2 只能算一个
				if (i == sqrt_N && n / i == i) {
					sum += 1;
				} else {
					sum += 2;
				}
			}
		}
		return sum;

	}
}
